|
In mathematics, a linear order, total order, simple order, or (non-strict) ordering is a binary relation on some set ''X'', which is transitive, antisymmetric, and total (this relation is denoted here by infix ≤). A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain. If ''X'' is totally ordered under ≤, then the following statements hold for all ''a'', ''b'' and ''c'' in ''X'': : If ''a'' ≤ ''b'' and ''b'' ≤ ''a'' then ''a'' = ''b'' (antisymmetry); : If ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity); : ''a'' ≤ ''b'' or ''b'' ≤ ''a'' (totality). Antisymmetry eliminates uncertain cases when both ''a'' precedes ''b'' and ''b'' precedes ''a''. A relation having the property of "totality" means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name ''linear''. ''Totality'' also implies reflexivity, i.e., ''a'' ≤ ''a''. Therefore, a total order is also a partial order. The partial order has a weaker form of the third condition. (It requires only reflexivity, not totality.) An extension of a given partial order to a total order is called a linear extension of that partial order. ==Strict total order== For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) relation <, called a strict total order, which can equivalently be defined in two ways: *''a'' < ''b'' if and only if ''a'' ≤ ''b'' and ''a'' ≠ ''b'' *''a'' < ''b'' if and only if not ''b'' ≤ ''a'' (i.e., < is the inverse of the complement of ≤) Properties: *The relation is transitive: ''a'' < ''b'' and ''b'' < ''c'' implies ''a'' < ''c''. *The relation is trichotomous: exactly one of ''a'' < ''b'', ''b'' < ''a'' and ''a'' = ''b'' is true. *The relation is a strict weak order, where the associated equivalence is equality. We can work the other way and start by choosing < as a transitive trichotomous binary relation; then a total order ≤ can equivalently be defined in two ways: *''a'' ≤ ''b'' if and only if ''a'' < ''b'' or ''a'' = ''b'' *''a'' ≤ ''b'' if and only if not ''b'' < ''a'' Two more associated orders are the complements ≥ and >, completing the quadruple . We can define or explain the way a set is totally ordered by any of these four relations; the notation implies whether we are talking about the non-strict or the strict total order. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Total order」の詳細全文を読む スポンサード リンク
|